home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / cool / ge_cool.lha / GE_COOL2.1 / man / oldman3 / Hash_Table.3T < prev    next >
Text File  |  1992-06-26  |  10KB  |  320 lines
  1. .TH HASH_TABLE
  2. .SH NAME
  3. Hash_Table<Ktype,Vtype>\f1  A dynamic, parameterized hash table
  4. .SH SYNOPSIS
  5. #include <cool/Hash_Table.h>
  6. .SH DESCRIPTION
  7. The \f3Hash_Table<Ktype,VType>\f1 class is publicly derived from the
  8.  Hash_Table 
  9. class and implements hash tables of user-specified types for both the key and 
  10. the value. This is accomplished by using the parameterized type capability of
  11.  
  12.  C++ . 
  13. The 
  14.  Hash_Table 
  15. class is dynamic in nature. Its size (that is, the number 
  16. of buckets in the table) is always a prime number. Each bucket holds eight 
  17. items. No holes are left in a bucket; if a key/value pair is removed from the 
  18. middle of a bucket, the following entries are moved up. When a hash on a key 
  19. ends up in a bucket that is full, the table is enlarged. 
  20. .SH Base Classes
  21.  Hash_Table, 
  22. .SH Friend Classes
  23. None
  24. .SH Constructors
  25. .TP
  26. \f3Hash_Table<Ktype,Vtype> ();\f1
  27. Allocates a hash table of the default size (three buckets).
  28. .TP
  29. \f3Hash_Table<Ktype,Vtype> \f3(unsigned long \f2number\f3);\f1
  30. Allocates a hash table with at least enough buckets for 
  31.  number 
  32. entries.
  33. .TP
  34. \f3Hash_Table<Ktype,Vtype> (const Hash_Table<Ktype,Vtype>& ht\f3);\f1
  35. Duplicates the size and entries of another hash table object 
  36.  ht .
  37. .SH Member Functions
  38. .TP
  39.  inline long capacity () const;
  40. Returns the maximum number of entries that the hash table can hold.
  41. .TP
  42.  void clear ();
  43. Removes all entries from the hash table and adjusts the appropriate counts.
  44. .TP
  45.  inline Hash_Table_state& current_position () const;
  46. Returns a reference to the state information associated with the current 
  47. position. This function should be used with the \f3Iterator<Type>\f1 class to save 
  48. and restore the current position, thus facilitating multiple iterators over an 
  49. instance of hash table.
  50. .TP
  51. \f3Boolean find (const Ktype& key\f3);\f1
  52. Searches the hash table for 
  53.  key 
  54. and returns 
  55.  
  56.  TRUE 
  57. if found; otherwise, this 
  58. function returns 
  59.  
  60.  FALSE . 
  61. If 
  62.  key 
  63. is found, this function sets the current 
  64. position to the key/value entry; otherwise, this function invalidates the 
  65. current position.
  66. .TP
  67. \f3Boolean get (const Ktype& key, Vtype& value\f3);\f1
  68. Calculates the hash value for 
  69.  key 
  70. and returns the value associated with that 
  71. key in the table by copying it to 
  72.  value . 
  73. This function sets the current 
  74. position to the key/value pair. If 
  75.  key 
  76. is found, this function returns 
  77.  
  78.  TRUE ; 
  79. otherwise, this function returns 
  80.  
  81.  FALSE .
  82. .TP
  83.  inline long get_bucket_count () const;
  84. Returns the prime number of buckets currently allocated for the hash table.
  85. .TP
  86. \f3inline int get_count_in_bucket (long \f2n\f3) const;\f1
  87. Returns the number of keys currently hashed to the zero-relative nth bucket.
  88.  
  89. .TP
  90. \f3Boolean get_key (const Vtype& value, Ktype& key\f3);\f1
  91. Searches the table for 
  92.  value . 
  93. If found, this function copies the associated key 
  94. into 
  95.  key , 
  96. sets the current position to the key/value pair, and returns
  97.  
  98.  TRUE .
  99. If 
  100.  value 
  101. is not found in the hash table, this function invalidates the current 
  102. position and returns 
  103.  
  104.  FALSE .
  105. .TP
  106.  inline Boolean is_empty () const;
  107. Returns 
  108.  
  109.  TRUE
  110. if the hash table contains no entries; otherwise, this function 
  111. returns 
  112.  
  113.  FALSE .
  114. .TP
  115. \f3const Ktype& \f3key ();\f1
  116. Returns the key of the key/value pair at the current position. If the current 
  117. position is invalid, an 
  118.  \f3\f3Error\f1\f1 
  119. exception is raised.
  120. .TP
  121.  inline long length () const;
  122. Returns the number of entries in the hash table.
  123. .TP
  124.  Boolean next ();
  125. Advances the current position pointer to the next entry in the hash table and 
  126. returns 
  127.  
  128.  TRUE . 
  129. If the current position is invalid, this function advances to the 
  130. first entry and returns 
  131.  
  132.  TRUE . 
  133. If advancing past the last entry in the hash 
  134. table, this function invalidates the current position and returns 
  135.  
  136.  FALSE .
  137. .TP
  138. \f3Hash_Table<Ktype,Vtype>& \f3operator= (const Hash_Table<Ktype,Vtype>& ht\f3);\f1
  139. Overloads the assignment operator for the class and assigns one hash table 
  140. object to have the value of another by duplicating the size and entries. This 
  141. function invalidates the current position of the object.
  142. .TP
  143. \f3Boolean operator== (const Hash_Table<Ktype,Vtype>& ht\f3);\f1
  144. Overloads the equality operator for the hash table class. This function returns
  145.  
  146.  TRUE
  147. if the tables have the same number of buckets with the same key/value 
  148. pairs; otherwise, this function returns 
  149.  
  150.  FALSE .
  151. .TP
  152. \f3inline Boolean operator!= (const Hash_Table<Ktype,Vtype>& ht\f3);\f1
  153. Overloads the inequality operator for the hash table class. This function 
  154. returns 
  155.  
  156.  TRUE 
  157. if the tables have a different number of buckets or different 
  158. key/value pairs; otherwise, this function returns 
  159.  FALSE .
  160. .TP
  161.  Boolean prev ();
  162. Moves the current position pointer to the previous entry in the hash table and 
  163. returns
  164.  
  165.  TRUE . 
  166. If the current position is invalid, this function moves to the 
  167. last entry and returns 
  168.  
  169.  TRUE . 
  170. If moving to the previous entry passes the first 
  171. entry in the hash table, this function invalidates the current position and 
  172. returns
  173.  
  174.  FALSE .
  175. .TP
  176. \f3Boolean put (const Ktype& key\f3, const Vtype& value\f3);\f1
  177. Searches the hash table for 
  178.  key 
  179. and puts the corresponding key/value pair into 
  180. the hash table. If
  181.  key 
  182. is not there, the key/value pair is added and 
  183.  
  184.  TRUE
  185. is returned; otherwise, if
  186.  key 
  187. is already there, this function updates the value 
  188. with 
  189.  value 
  190. and returns 
  191.  
  192.  FALSE . 
  193. If the bucket determined by the hash is full, the 
  194. table grows and the key/value pairs are rehashed and inserted. This function 
  195. sets the current position to the key/value pair.
  196. .TP
  197.  Boolean remove ();
  198. Removes the key/value at the current position and returns 
  199.  
  200.  TRUE . 
  201. This function 
  202. sets the current position to the entry immediately following the entry removed 
  203. if in the same bucket; otherwise, this function invalidates the current 
  204. position. If the current position is invalid, an 
  205.  \f3\f3Error\f1\f1 
  206. exception is raised and, 
  207. if the handler returns, this function returns
  208.  
  209.  FALSE .
  210.  
  211. .TP
  212. \f3Boolean remove (const Ktype& key\f3);\f1
  213. Searches the hash table for 
  214.  key , 
  215. removes the indicated key/value pair from the 
  216. table, sets the current position to the old location of the key/value pair, and 
  217. returns 
  218.  
  219.  TRUE . 
  220. If key is not found in the hash table, this function returns 
  221.  
  222.  FALSE .
  223. .TP
  224.  inline void reset ();
  225. Invalidates the current position.
  226. .TP
  227. \f3Boolean resize (long \f2number\f3);\f1
  228. Resizes the hash table for at least the indicated number of entries. If a 
  229. growth ratio has been selected and it satisfies the resize request, the table 
  230. is grown by this ratio. This function invalidates the current position. If the 
  231. resize value is zero or negative, an 
  232.  \f3\f3Error\f1\f1 
  233. exception is raised.
  234. .TP
  235. \f3inline void set_hash (\f2Hash h\f3);\f1
  236. Updates the hash function for this instance of hash table. 
  237.  Hash 
  238. is a function 
  239. of type 
  240.  unsigned long 
  241. (\f2*Function\f1) (\f3const Ktype&\f1). If the key is of type 
  242.  char* , 
  243. the hash is the result of successively exclusive-or-ing each byte with the 
  244. current hash value shifted left seven bits. If the key is not of type 
  245.  char* , 
  246. the default hash function is the computation of a 32-bit value shifted left 
  247. three bits with the result then modulo the prime number of buckets. If the size 
  248. of \f2(Ktype)\f1 is greater than four bytes, the 32-bit value is computed by 
  249. successively exclusive-or-ing 32-bit values for the length of the key.
  250. .TP
  251. \f3void set_key_compare (\f2Hash_Key_Compare \f3= NULL);\f1
  252. Updates the key compare function for this instance of hash table. 
  253.  Hash_Key_Compare 
  254. is a function of type 
  255.  Boolean 
  256. (\f2*Function\f1)(\f3const Ktype&\f1, \f3const Ktype&\f1). If no argument is provided, the 
  257.  operator== 
  258. for 
  259.  Ktype , 
  260. the key over 
  261. which the class is parameterized, is used. If the key is a 
  262.  char* , 
  263. a 
  264.  String , 
  265. or a 
  266.  Gen_String , 
  267. the default compare function is a string comparison.
  268. .TP
  269. \f3inline void set_ratio (\f2float\f3);\f1
  270. Updates the growth ratio for this instance of the hash table to the specified 
  271. value.  When a hash table needs to grow, the current size is multiplied by the 
  272. ratio to determine the new size. If 
  273.  ratio 
  274. is negative, an 
  275.  \f3\f3Error\f1\f1 
  276. exception is raised.
  277. .TP
  278. \f3void set_value_compare (\f2Hash_Value_Compare \f3= NULL);\f1
  279. Updates the value compare function for this instance of hash table. 
  280.  Hash_Value_Compare 
  281. is a function of type 
  282.  Boolean 
  283. (\f2*Function\f1)(\f3const Vtype&\f1, \f3const Vtype&\f1). If no argument is provided, the
  284.  operato== 
  285. for 
  286.  Vtype , 
  287. the value over 
  288. which the class is parameterized, is used.
  289. .TP
  290. \f3const Vtype& \f3value ();\f1
  291. Returns a reference to the value of the key/value pair at the current position. 
  292. If the current position is invalid, an 
  293.  \f3\f3Error\f1\f1 
  294. exception is raised.
  295. .SH Friend Functions
  296. .TP
  297. \f3friend ostream& operator<< (ostream& \f2os\f3, const Hash_Table<Ktype,Vtype>& ht\f3);\f1
  298. Overloads the output operator for a reference to a 
  299.  Hash_Table< Ktype,Vtype > 
  300. object. This function provides a formatted output with key/value pairs printed 
  301. one per line.
  302. .TP
  303. \f3inline friend ostream& operator<< (ostream& \f2os\f3, const Hash_Table<Ktype,Vtype>* ht\f3);\f1
  304. Overloads the output operator for a pointer to a 
  305.  Hash_Table< Ktype,Vtype >  
  306. object. This function provides a formatted output with key/value pairs printed 
  307. one per line.
  308. .SH COPYRIGHT
  309.  
  310. Copyright (C) 1991 Texas Instruments Incorporated.
  311.  
  312. Permission is granted to any individual or institution to use, copy, modify,
  313. and distribute this software, provided that this complete copyright and
  314. permission notice is maintained, intact, in all copies and supporting
  315. documentation.
  316.  
  317. Texas Instruments Incorporated provides this software "as is" without
  318. express or implied warranty.
  319.  
  320.